1. Technical Field of the Invention
The present invention relates to computers and, more particularly, to spatial footprint prediction of usage of cache-lines from main memory by a computer.
2. Background Art
Caches hold a relatively small amount of data that can be accessed relatively quickly by a processor. By contrast, main memory holds a relatively large amount of data that is accessed relatively slowly by a processor. Caches are organized into cache-lines. Typically, the smallest replaceable unit in a cache is a cache-line. In many computer systems, a cache-line has 32 or 64 bytes. There are at least two advantages to having large cache-lines. First, a tag is used to identify each cache-line. Therefore, the larger the cache-line, the fewer the number of tags and associated resources that are used for a given amount of data stored in the cache. Second, there is substantial latency in fetching data from main memory. Therefore, it is desirable to reduce the number of fetches from memory. In most applications, there is spatial locality with respect to memory references used. That is, if a program uses data from a reference to address X, there is a fair likelihood that in the near future the program will also use data from a reference to adjacent addresses X+1 and/or Xxe2x88x921. Therefore, by fetching large cache-lines, there is a likelihood that fewer caches lines will need to be access from main memory.
In general larger cache-lines improve performance when spatial locality is available, but may hurt performance by prefetching unnecessary data when there is no spatial locality. For example, a piece of data requested by the processor may have only four bytes. If there is no spatial locality, there may be 28 wasted bytes, in the case of a 32-byte cache-line. Further, accessing the four bytes may have caused eviction of other bytes from the evicted line that would have been used resulting in another access from main memory. Because spatial locality may differ between different applications as well as between different sequences of memory references within a single application, cache designers generally choose a line size with the best average performance across a broad range of reference patterns. This approach wastes bandwidth when a sequence of memory references does not exhibit spatial locality. Further, the cache is polluted by cache-lines that are not needed because the cache-lines can be written over data that would be used.
The present invention is directed to overcoming or reducing the effect of one or more the above-recited problems with access to main memory.
A spatial footprint predictor includes a mechanism to measure spatial footprints of nominating cache-lines and hold the footprints. In some embodiments, the mechanism includes an active macro-block table (AMBT) to measure the spatial footprints and a spatial footprint table (SFT) to hold the spatial footprints. In other embodiments, the mechanism includes a macro-block table (MBT) in which macro-blocks may be active or inactive.